|
In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vertices ''V'' has ''n'' elements then the Tutte matrix is an ''n'' × ''n'' matrix A with entries : where the ''x''''ij'' are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables ''xij'', ''i < j'' ): this coincides with the square of the pfaffian of the matrix ''A'' and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the Tutte polynomial of ''G''.) The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph. ==References== * * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tutte matrix」の詳細全文を読む スポンサード リンク
|